package interview.array;

import java.util.HashMap;
import java.util.Map;

/**
 * 同一个数组元素不能使用两遍
 * 返回数组下标
 * Created by yzy on 2021-02-06 14:19
 */
public class TwoSum {

    /**
     * 使用一个Map存储遍历过的数值。就不需要暴力的一直重复遍历了
     * Map: key=数组值, val=数组下标
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> valMap = new HashMap<>(); // key=值, val=下标
        for(int i=0; i<nums.length; i++){
            int tmp = target - nums[i];
            Integer otherIdx = valMap.get(tmp);
            if(otherIdx != null){
                return new int[]{i, otherIdx};
            }else{
                valMap.put(nums[i], i);
            }
        }
        return null;
    }

    public int[] twoSum_slow(int[] nums, int target) {
        int[] res = new int[2];
        for(int i=0; i<nums.length-1; i++){
            for(int j=i+1; j<nums.length; j++){
                if(nums[j] == target-nums[i]){
                    res[0] = i;
                    res[1] = j;
                    break;
                }
            }
        }
        return res;
    }
}
